1. Field of the Invention
This invention relates to operation of network switches under traffic overload conditions, and in particular to dropping of packets as a switch becomes congested.
2. Background Information
Modern computer networks are often designed using the TCP/IP protocol to transfer data packets between end stations. The TCP/IP packets transferred between end stations are often converted to fixed length packets for transfer over a trunk line within the computer network, for example ATM networks are often used as trunk lines in the computer network. The ATM portion of the network uses switches designed to switch ATM cells. Congestion of cell traffic within an ATM switch may develop when the network carries a heavy traffic load.
A switch, for example an ATM switch, is often designed with linecards attaching to the external computer network, and attaching to a “switching fabric” within the switch. The switching fabric, such as an ATM switching fabric, is often implemented in a few computer chips. The computer chips have an internal structure which is not available to the switch designer. The switch designer only has control of the input and output parameters of a switch so that a route from an input linecard to an output linecard may be built through the switch for each cell as it arrives at the switch, and the switch designer has no control or access to the internal structure of the switching fabric chips.
The internal structure of the switching fabric maintains queues of cells as they await the various operations needed to operate the switching fabric. When congestion develops in the switch, these queues may fill so that there is no room to store the next arriving cell. The next arriving cell is then dropped. A lost cell in the switching fabric causes loss of a TCP/IP packet at the point in the network where the TCP/IP packets are re-assembled from the ATM cells. A lost TCP/IP packet causes the TCP/IP protocol to respond, first by re-transmitting the lost packet, and second by reducing the transmission rate of the transmitter. When many end stations are transmitting packets which contribute to the cell overflow in the switch, then packets from all of the end stations may be dropped by the switch at about the same time. The transmitters then begin re-transmitting the lost packets at about the same time. This retransmission at about the same time leads to unwanted synchronization between transmitting stations of the computer network.
Unwanted synchronization of a computer network due to loss of packets at a congested switch has been reduced by randomly dropping packets in the traffic stream using an algorithm referred to as the Random Early Detection (RED) algorithm. The RED algorithm is described by S. Floyd and V. Jacobson in their paper “Random Early Detection Gateways for Congestion Avoidance” published in the IEEE/ACM Transactions on Networking, Vi, N4, pp. 397–412, in August 1993, all disclosures of which are incorporated herein by reference. Also, further features of the RED algorithm are described in the paper by V. Jacobson, K. Nichols, K. Poduri, titled “RED in A New Light”, unpublished but widely circulated, all disclosures of which are incorporated herein by reference. The RED algorithm uses lengths of queues within the switching fabric as input parameters to the RED algorithm.
However, when a switching fabric is implemented in a set of commercial computer chips, the queues within the switching fabric are not available to the switch designer. The switch designer then cannot implement the RED algorithm.
There is needed an improved method for handling lost ATM cells, and lost packets, in a switch of a computer network.